Mesh Simplification Using Quadratic Error Metric </head> <body> <font face="times new roman" size="6" color="black"> Mesh Simplification Using Quadratic Error Metric <br> Daniel Bussone </font> <font face="times new roman" size="4" color="black"> <br><br><b>Overview:</b> <p>The pursuit of highly detailed models and meshes has always been a goal of computer graphics, but rendering these images is taxing on hardware. Detailed meshes are often too time consuming to render in real-time. Simplifying these meshes while retaining a sufficient level of detail is paramount for timely rendering. Mesh simplification using the quadratic error metric attempts to address this.<br><br> The algorithm attempts to progressively remove information from the mesh while retaining its geometry. Each vertex computes a minimum error for collapsing one of its edges. It does this by creating a matrix based on its adjacent triangles. The vertex's matrix is combined with a connecting edge vertex's matrix to find the ideal position for an edge colapse. This position is compared against the original vertex to compute a cost for collapsing the edge and moving the vertex. These costs are held in a priority queue so that the edge with the least error will collapse first. I created a error threshold for which a vertex would not collapse its edge if its error was too high (it would disturb the topology more than desired). I also allowed for an incrementation of the error threshold for further simplification. </p> Bunny with 10,000 Triangles <br> <img src="Bunny10000Tri2.jpg" width="750" height="500"> <br>Bunny with 6,477 Triangles (65% original size)<br> <img src="Bunny6477Tri2.jpg" width="750" height="500"> <br>Bunny with 1,502 Triangles (15% original size)<br> <img src="Bunny1502Tri2.jpg" width="750" height="500"> <br>Bunny with 694 Triangles (7% original size)<br> <img src="Bunny694Tri2.jpg" width="750" height="500"> <br>Bunny with 229 Triangles (2% original size)<br> <img src="Bunny229Tri2.jpg" width="750" height="500"> <br>Bunny with 173 Triangles (1.7% original size)<br> <img src="Bunny173Tri2.jpg" width="750" height="500"> <br><br>The mesh maintains its bunny shape all the way through to under 2% the original number of polygons.<br><br> <br>Gargoyle with 2,000 Triangles<br> <img src="Gargoyle2000Tri2.jpg" width="500" height="650"> <br>Gargoyle with 1,170 Triangles<br> <img src="Gargoyle1170Tri2.jpg" width="500" height="650"> <br>Gargoyle with 608 Triangles<br> <img src="Gargoyle608Tri2.jpg" width="500" height="650"> <br>Gargoyle with 300 Triangles<br> <img src="Gargoyle300Tri2.jpg" width="500" height="650"><br><br><br> The gargoyle does not begin to lose the topology of his wings until it is decimated to about 15% of its original size.<br> <br><b>Conclusion:</b><br><br> Decimation of meshes using the quadratic error metric seems to be a very useful way of greatly reducing the data without losing too much detail in the model. For larger models like the 20,000 face bunny, the quadratic error metric can reduce the storage needs by 85 to 90 percent before a noticeable difference in model shape is obtained. This could allow developers to run real-time simulations or games with a much higher frame rate than with the original models.<br> <br><b>Problems:</b><br><br> Because I used a triangle based data structure, I was not able to import square based meshes into my program. This prevented me from using files from 3ds Max which were square based meshes. In the future I may have to create a new data structure to handle these mesh types.<br> <br><b>Provided Executable:</b><br><br> The provided executable is my program's attempt at simplifying a 2,000 triangle face gargoyle mesh. The number '4' is used to simplify the mesh. Press and hold to further simplify.<br> <a href="Gargoyle.zip">Executable</a> <br><br><b>Resources:</b><br><br> <a href="http://mgarland.org/research/quadrics.html">Quadratic Error Metrics</a> </font> </body> </html>